import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Test {
    public static void main(String[] args) {

    }
    public static void main5(String[] args) {
        Set<Integer> set = new HashSet<>();
        System.out.println(set.contains(1));
        List<Integer> list = new LinkedList<>();
        list.size();
        list.get(0);
    }
    public static void main4(String[] args) {
        Stack<Character> stack = new Stack<>();
        List<Integer> s = new ArrayList<>();
        s.add(1);
        s.add(2);
        System.out.println(s.get(0));
        System.out.println(s.get(s.size() - 1));
    }
    public static void main3(String[] args) {
        List<TreeNode> ret = allPossibleFBT(5);

        //打印
        for (TreeNode tmp : ret) {
            printTree(tmp);
            System.out.println();
        }
    }

    public static void printTree(TreeNode node) {
        if (node == null) {
            System.out.print("null ");
        } else {
            System.out.print(node.val + " ");
            printTree(node.left);
            printTree(node.right);
        }
    }

    public static List<TreeNode> allPossibleFBT(int n) {
        if(n % 2 == 0)return new ArrayList<>();   // 偶数个节点，不构成任何真二叉树
        List<TreeNode>[] dp = new ArrayList[n+1];	// dp[i]存储的是节点数为i的所有可能真二叉树集合
        for(int i = 0; i <= n; i++){
            dp[i] = new ArrayList<>();
        }
        dp[1].add(new TreeNode());	// 节点数为1的只有一种情况
        for(int i = 3; i <= n; i += 2){		// 枚举每一种节点数i
            for(int j = 1; j < i; j += 2){	// 枚举其左子树节点数为j
                for(TreeNode leftNode: dp[j]){	// 从dp[j]中获取不同的子树作为左子树
                    for(TreeNode rightNode: dp[i - 1 - j]){	// 右子树节点就应该为总节点数i - 根节点1 - 左子节点j，并枚举
                        dp[i].add(new TreeNode(0, leftNode, rightNode));
                    }
                }
            }
        }
        return dp[n];
    }


    public static void main1(String[] args) {
        List<TreeNode>[] dp = new ArrayList[6];
        for (int i = 0; i < 6; i++) {
            dp[i] = new ArrayList<>();
        }
        TreeNode leftNode = new TreeNode(1);
        TreeNode rightNode = new TreeNode(2);
        TreeNode root = new TreeNode(0);
        dp[0].add(new TreeNode(0, leftNode, rightNode));

        for (TreeNode tmp : dp[0]) {
            System.out.print(tmp.val + " ");
            if (tmp.left != null) {
                System.out.print(tmp.left.val + " ");
            }
            if (tmp.right != null) {
                System.out.println(tmp.right.val + " ");
            }
        }

        System.out.println("\n" + dp[0]);
    }
}
